package _剑指offer.二叉树;

import util.TreeNode;
import org.junit.Test;

/**
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 * 
 * 若树 B 是树 A 的子结构，则子结构的根节点可能为树 A 的任意一个节点。因此，判断树 B 是否是树 A 的子结构，需完成以下两步工作：
 *      1、先序遍历树 A 中的每个节点 n_A 。（对应函数 isSubStructure(A, B)）
 *          isSubStructure(A, B)
 *              1）特例
 *              当 树 A 为空 或 树 B 为空 时，直接返回 false ；
 *              2）返回值： 若树 B 是树 A 的子结构，则必满足以下三种情况之一，因此用或 || 连接
 *              以 节点 AA 为根节点的子树 包含树 BB ，对应 recur(A, B)
 *              树 B 是 树 A 左子树 的子结构，对应 isSubStructure(A.left, B)
 *              树 B 是 树 A 右子树 的子结构，对应 isSubStructure(A.right, B)
 *              
 *      2、判断树 A 中 以 n_A 为根节点的子树 是否包含树 B 。（对应函数 recur(A, B)）
 *          recur(A, B)
 *              1）终止条件
 *              当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true 
 *              当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false
 *              当节点 A 和 B 的值不同：说明匹配失败，返回 false
 *              2）返回值
 *              判断 A 和 B 的左子节点是否相等，即 recur(A.left, B.left)
 *              判断 A 和 B 的右子节点是否相等，即 recur(A.right, B.right)
 */
public class _26_树的子结构 {
    @Test
    public void main() {
        Integer[] input1 = new Integer[]{3,4,5,1,2};
        Integer[] input2 = new Integer[]{4,1};
        TreeNode root1 = TreeNode.getTreeFromArray(input1);
        TreeNode root2 = TreeNode.getTreeFromArray(input2);
        System.out.println("isSubStructure(root1, root2) = " + isSubStructure(root1, root2));
    }
    
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        return isSubStructure(A.left, B) || isSubStructure(A.right, B) || recur(A, B);
    }
    
    private boolean recur(TreeNode A, TreeNode B) {
        if (B == null) return true;
        if (A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}
